后面枚举 的过程可以看作将 个相同的球放进 个不同的盒子,且不能有空盒的方案数,利用插板法可得:
那么原式即为:
#include <cstdio>
const int MAXN = 1e5 , Mod = 1e9 + 7;
int Quick_pow( int x , int po ) { int p = 1; for( ; po ; po >>= 1 , x = 1ll * x * x % Mod ) if( po & 1 ) p = 1ll * p * x % Mod; return p; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
mu[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ prnum ] = i;
mu[ i ] = -1;
}
for( int j = 1 ; j <= prnum && i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
}
int fac[ MAXN + 5 ] , ivf[ MAXN + 5 ];
void Init( ) {
fac[ 0 ] = 1;
for( int i = 1 ; i <= MAXN ; i ++ ) fac[ i ] = 1ll * fac[ i - 1 ] * i % Mod;
ivf[ MAXN ] = Inv( fac[ MAXN ] );
for( int i = MAXN ; i >= 1 ; i -- ) ivf[ i - 1 ] = 1ll * ivf[ i ] * i % Mod;
}
int C( int n , int m ) {
return n < m ? 0 : 1ll * fac[ n ] * ivf[ m ] % Mod * ivf[ n - m ] % Mod;
}
int Solve( int n , int f ) {
int Ans = 0;
for( int d = 1 ; d * d <= n ; d ++ )
if( n % d == 0 ) {
Ans = ( Ans + mu[ d ] * C( n / d - 1 , f - 1 ) ) % Mod;
if( d * d != n ) Ans = ( Ans + mu[ n / d ] * C( d - 1 , f - 1 ) ) % Mod;
}
return ( Ans + Mod ) % Mod;
}
int q , n , f;
int main( ) {
Init(); sieve();
scanf("%d",&q);
while( q -- ) {
scanf("%d %d",&n,&f);
printf("%d\n", Solve( n , f ) );
}
return 0;
}